"""
Dijkstra算法实现和TSP优化
"""
import heapq
import itertools
from typing import Dict, List, Tuple, Optional, Set
from decimal import Decimal


class MultiFactorWeight:
    """多因素权重计算"""
    
    def __init__(self, distance_weight=0.6, cost_weight=0.4, time_weight=0.0, popularity_weight=0.0):
        self.distance_weight = distance_weight  # 距离权重
        self.cost_weight = cost_weight          # 费用权重
        self.time_weight = time_weight          # 时间权重
        self.popularity_weight = popularity_weight  # 热度权重
        
        # 归一化常量（可根据实际数据调整）
        self.MAX_DISTANCE = 100.0  # 最大距离（公里）
        self.MAX_COST = 1000.0     # 最大费用（元）
        self.MAX_TIME = 480         # 最大时间（分钟，8小时）
        self.MAX_POPULARITY = 100   # 最大热度

    def calculate_weight(self, distance: float, cost: float, time: int = 0, popularity: int = 0) -> float:
        """
        计算综合权重
        :param distance: 距离（公里）
        :param cost: 费用（元）
        :param time: 时间（分钟）
        :param popularity: 热度
        :return: 综合权重值（越小越好）
        """
        normalized_distance = min(distance / self.MAX_DISTANCE, 1.0)
        normalized_cost = min(cost / self.MAX_COST, 1.0)
        normalized_time = min(time / self.MAX_TIME, 1.0) if self.MAX_TIME > 0 else 0
        normalized_popularity = min(popularity / self.MAX_POPULARITY, 1.0) if self.MAX_POPULARITY > 0 else 0
        
        # 热度越高，权重越小（取反）
        popularity_factor = (1 - normalized_popularity) if self.popularity_weight > 0 else 0
        
        weight = (
            normalized_distance * self.distance_weight +
            normalized_cost * self.cost_weight +
            normalized_time * self.time_weight +
            popularity_factor * self.popularity_weight
        )
        
        return weight


class TravelDijkstra:
    """旅游路线Dijkstra算法实现"""
    
    def __init__(self, graph: Dict[int, Dict[int, Dict]], budget_constraint: float, 
                 weight_config: Optional[MultiFactorWeight] = None,
                 start_time: Optional[str] = None,
                 max_total_time: Optional[int] = None,
                 attractions_info: Optional[Dict] = None):
        """
        初始化算法
        :param graph: 图数据结构 {节点ID: {邻居节点ID: {distance, cost, time, popularity}}}
        :param budget_constraint: 预算约束
        :param weight_config: 权重配置
        :param start_time: 开始时间（格式：HH:MM）
        :param max_total_time: 最大总时间（分钟），None表示不限制
        :param attractions_info: 景点信息字典 {attraction_id: Attraction对象}
        """
        self.graph = graph
        self.budget = budget_constraint
        self.weight_config = weight_config or MultiFactorWeight()
        self.start_time = start_time  # 开始时间字符串 "HH:MM"
        self.max_total_time = max_total_time  # 最大总时间（分钟）
        self.attractions_info = attractions_info or {}  # 景点信息
        self.visited = set()
        self.distances = {}  # 最短权重距离
        self.previous_nodes = {}
        self.remaining_budget = {}  # 到达每个节点时的剩余预算
        self.total_costs = {}  # 到达每个节点的总费用
        self.total_distances = {}  # 到达每个节点的总距离
        self.total_times = {}  # 到达每个节点的总时间（分钟）
        
    def find_optimal_routes(self, start_attraction: int, 
                           must_visit: Optional[List[int]] = None,
                           end_attraction: Optional[int] = None) -> Tuple[List[int], float, float, float]:
        """
        查找最优路线
        :param start_attraction: 起始景点ID
        :param must_visit: 必须访问的景点ID列表
        :param end_attraction: 目标景点ID（可选，如果不指定则寻找包含所有必访景点的路线）
        :return: (最优路线, 总权重, 总费用, 总距离)
        """
        if start_attraction not in self.graph:
            raise ValueError(f"起始景点 {start_attraction} 不存在于图中")
        
        must_visit = must_visit or []
        
        # 初始化
        self._initialize_algorithm(start_attraction)
        
        # 使用优先队列（最小堆）
        # 队列元素：(权重, 当前节点, 剩余预算, 路径, 当前总时间)
        initial_time = self._parse_time_to_minutes(self.start_time) if self.start_time else 0
        priority_queue = [(0, start_attraction, self.budget, [start_attraction], initial_time)]
        
        best_route = None
        best_weight = float('inf')
        visited_routes = set()
        
        while priority_queue:
            current_weight, current_node, current_budget, current_path, current_time = heapq.heappop(priority_queue)
            
            # 检查是否已访问过该路径状态
            route_key = (current_node, tuple(sorted(current_path)), round(current_budget, 2), current_time)
            if route_key in visited_routes:
                continue
            visited_routes.add(route_key)
            
            # 检查时间约束
            if self.max_total_time and current_time > self.max_total_time:
                continue
            
            # 检查是否满足必访景点要求
            if self._check_must_visit(current_path, must_visit):
                # 如果指定了目标景点，检查是否到达
                if end_attraction is None or current_node == end_attraction:
                    if current_weight < best_weight:
                        best_weight = current_weight
                        best_route = current_path.copy()
                        continue
            
            # 如果指定了目标景点且已到达，跳过后续处理
            if end_attraction and current_node == end_attraction:
                continue
            
            # 遍历邻居节点
            if current_node not in self.graph:
                continue
                
            for neighbor, edge_data in self.graph[current_node].items():
                if neighbor in current_path:  # 避免重复访问
                    continue
                
                edge_cost = float(edge_data.get('cost', 0))
                edge_distance = float(edge_data.get('distance', 0))
                edge_time = edge_data.get('time', 0)  # 交通时间
                neighbor_popularity = edge_data.get('popularity', 0)
                
                # 检查预算约束
                if current_budget < edge_cost:
                    continue
                
                # 计算到达邻居节点的时间
                neighbor_attraction = self.attractions_info.get(neighbor)
                visit_time = neighbor_attraction.visit_time if neighbor_attraction and neighbor_attraction.visit_time else 60
                arrival_time = current_time + edge_time  # 到达时间
                # 开放时间等待逻辑（仅处理非跨天开放窗口）：到早则等待到开门
                adjusted_edge_time = edge_time
                if neighbor_attraction and neighbor_attraction.open_time and neighbor_attraction.close_time:
                    open_minutes = neighbor_attraction.open_time.hour * 60 + neighbor_attraction.open_time.minute
                    close_minutes = neighbor_attraction.close_time.hour * 60 + neighbor_attraction.close_time.minute
                    day_minutes = arrival_time % 1440
                    if close_minutes >= open_minutes:
                        # 正常窗口：到早则等待到开门；到晚则跳过
                        if day_minutes < open_minutes:
                            wait_time = open_minutes - day_minutes
                            arrival_time += wait_time
                            adjusted_edge_time += wait_time
                        elif day_minutes > close_minutes:
                            # 已过关门时间，无法访问
                            continue
                    else:
                        # 跨天窗口（例如 22:00-02:00）：开放区间为 [open, 1440) ∪ [0, close]
                        if not (day_minutes >= open_minutes or day_minutes <= close_minutes):
                            # 在关闭区间，需要等待到下一次开门
                            if day_minutes < open_minutes:
                                # 当天晚间开门
                                wait_time = open_minutes - day_minutes
                            else:
                                # 已过当天开门，等待到次日开门
                                wait_time = (1440 - day_minutes) + open_minutes
                            arrival_time += wait_time
                            adjusted_edge_time += wait_time
                departure_time = arrival_time + visit_time  # 离开时间
                
                # 检查时间约束
                if self.max_total_time and departure_time > self.max_total_time:
                    continue
                
                # 检查景点开放时间（跨天情况保持原有检查）
                if neighbor_attraction and not self._check_attraction_open_time(neighbor_attraction, arrival_time):
                    continue
                
                new_budget = current_budget - edge_cost
                new_distance = self.total_distances.get(current_node, 0) + edge_distance
                new_cost = self.total_costs.get(current_node, 0) + edge_cost
                new_time = departure_time
                
                # 计算权重
                edge_weight = self.weight_config.calculate_weight(
                    edge_distance, edge_cost, adjusted_edge_time, neighbor_popularity
                )
                new_weight = current_weight + edge_weight
                
                # 更新路径
                new_path = current_path + [neighbor]
                
                # 添加到优先队列
                heapq.heappush(priority_queue, (
                    new_weight,
                    neighbor,
                    new_budget,
                    new_path,
                    new_time
                ))
                
                # 更新记录
                if neighbor not in self.total_costs or new_cost < self.total_costs[neighbor]:
                    self.total_costs[neighbor] = new_cost
                    self.total_distances[neighbor] = new_distance
                    self.remaining_budget[neighbor] = new_budget
                    self.total_times[neighbor] = new_time
        
        if best_route is None:
            raise ValueError("未找到符合条件的路线")
        
        total_cost = sum(
            self.graph[best_route[i]][best_route[i+1]].get('cost', 0)
            for i in range(len(best_route) - 1)
        )
        total_distance = sum(
            self.graph[best_route[i]][best_route[i+1]].get('distance', 0)
            for i in range(len(best_route) - 1)
        )
        
        return best_route, best_weight, total_cost, total_distance
    
    def _initialize_algorithm(self, start_node: int):
        """初始化算法数据"""
        self.visited = set()
        self.distances = {node: float('inf') for node in self.graph}
        self.distances[start_node] = 0
        self.previous_nodes = {}
        initial_time = self._parse_time_to_minutes(self.start_time) if self.start_time else 0
        self.remaining_budget = {start_node: self.budget}
        self.total_costs = {start_node: 0}
        self.total_distances = {start_node: 0}
        self.total_times = {start_node: initial_time}
    
    def _check_must_visit(self, path: List[int], must_visit: List[int]) -> bool:
        """检查路径是否包含所有必访景点"""
        if not must_visit:
            return True
        return all(attraction_id in path for attraction_id in must_visit)
    
    def _parse_time_to_minutes(self, time_str: str) -> int:
        """
        将时间字符串转换为分钟数（从00:00开始）
        :param time_str: 时间字符串，格式：HH:MM
        :return: 分钟数
        """
        try:
            parts = time_str.split(':')
            if len(parts) != 2:
                return 0
            hours = int(parts[0])
            minutes = int(parts[1])
            return hours * 60 + minutes
        except (ValueError, AttributeError):
            return 0
    
    def _minutes_to_time_str(self, minutes: int) -> str:
        """
        将分钟数转换为时间字符串
        :param minutes: 分钟数（从00:00开始）
        :return: 时间字符串，格式：HH:MM
        """
        hours = minutes // 60
        mins = minutes % 60
        return f"{hours:02d}:{mins:02d}"
    
    def _check_attraction_open_time(self, attraction, arrival_time_minutes: int) -> bool:
        """
        检查景点在指定时间是否开放
        :param attraction: 景点对象
        :param arrival_time_minutes: 到达时间（分钟，从00:00开始）
        :return: 是否开放
        """
        if not attraction.open_time or not attraction.close_time:
            return True  # 如果没有设置开放时间，认为全天开放
        
        # 将TimeField转换为分钟数
        open_minutes = attraction.open_time.hour * 60 + attraction.open_time.minute
        close_minutes = attraction.close_time.hour * 60 + attraction.close_time.minute
        
        # 处理跨天情况（如22:00-02:00）
        if close_minutes < open_minutes:
            # 跨天开放
            return arrival_time_minutes >= open_minutes or arrival_time_minutes <= close_minutes
        else:
            # 正常情况
            return open_minutes <= arrival_time_minutes <= close_minutes


class DijkstraAlgorithm:
    """标准Dijkstra算法实现（用于简单最短路径）"""
    
    def __init__(self, graph: Dict[int, Dict[int, float]]):
        """
        初始化算法
        :param graph: 图数据结构 {节点: {邻居节点: 权重}}
        """
        self.graph = graph
        self.distances = {}
        self.previous_nodes = {}
        self.unvisited_nodes = []
    
    def find_shortest_path(self, start_node: int, end_node: int) -> Tuple[List[int], float]:
        """
        查找最短路径
        :param start_node: 起始节点
        :param end_node: 目标节点
        :return: (路径, 距离)
        """
        self._initialize_algorithm(start_node)
        
        while self.unvisited_nodes:
            current_node = self._get_closest_unvisited_node()
            if current_node == end_node:
                break
            self._update_neighbor_distances(current_node)
        
        if end_node not in self.previous_nodes and start_node != end_node:
            raise ValueError(f"无法从 {start_node} 到达 {end_node}")
        
        return self._build_path(end_node), self.distances[end_node]
    
    def _initialize_algorithm(self, start_node: int):
        """初始化算法数据"""
        self.distances = {node: float('inf') for node in self.graph}
        self.distances[start_node] = 0
        self.previous_nodes = {}
        self.unvisited_nodes = list(self.graph.keys())
    
    def _get_closest_unvisited_node(self) -> int:
        """获取距离最近的未访问节点"""
        unvisited = {node: self.distances[node] for node in self.unvisited_nodes}
        closest_node = min(unvisited, key=unvisited.get)
        self.unvisited_nodes.remove(closest_node)
        return closest_node
    
    def _update_neighbor_distances(self, current_node: int):
        """更新邻居节点的距离"""
        if current_node not in self.graph:
            return
        
        for neighbor, weight in self.graph[current_node].items():
            if neighbor not in self.unvisited_nodes:
                continue
            
            new_distance = self.distances[current_node] + weight
            if new_distance < self.distances[neighbor]:
                self.distances[neighbor] = new_distance
                self.previous_nodes[neighbor] = current_node
    
    def _build_path(self, end_node: int) -> List[int]:
        """构建路径"""
        path = []
        current = end_node
        
        while current is not None:
            path.insert(0, current)
            current = self.previous_nodes.get(current)
        
        return path


class TSPOptimizer:
    """TSP（旅行商问题）优化器 - 用于优化必访景点的访问顺序"""
    
    def __init__(self, graph: Dict[int, Dict[int, Dict]], weight_config: Optional[MultiFactorWeight] = None):
        """
        初始化TSP优化器
        :param graph: 图数据结构 {节点ID: {邻居节点ID: {distance, cost, time, popularity}}}
        :param weight_config: 权重配置（用于计算路径权重）
        """
        self.graph = graph
        self.weight_config = weight_config or MultiFactorWeight()
        self.MAX_ATTractions_FOR_BRUTEFORCE = 6  # 超过6个景点使用启发式算法
    
    def optimize_visit_order(self, start_attraction: int, must_visit: List[int]) -> List[int]:
        """
        优化必访景点的访问顺序
        :param start_attraction: 起始景点ID
        :param must_visit: 必访景点ID列表
        :return: 优化后的访问顺序（包含起始景点）
        """
        if not must_visit:
            return [start_attraction]
        
        # 如果必访景点数量较少，使用暴力搜索（全排列）
        if len(must_visit) <= self.MAX_ATTractions_FOR_BRUTEFORCE:
            return self._bruteforce_optimize(start_attraction, must_visit)
        else:
            # 使用启发式算法（最近邻 + 2-opt优化）
            return self._heuristic_optimize(start_attraction, must_visit)
    
    def _bruteforce_optimize(self, start_attraction: int, must_visit: List[int]) -> List[int]:
        """
        暴力搜索最优顺序（全排列）
        适用于少量景点（<=6个）
        """
        if not must_visit:
            return [start_attraction]
        
        best_order = None
        best_weight = float('inf')
        
        # 生成所有可能的排列
        for perm in itertools.permutations(must_visit):
            order = [start_attraction] + list(perm)
            total_weight = self._calculate_path_weight(order)
            
            if total_weight < best_weight:
                best_weight = total_weight
                best_order = order
        
        return best_order if best_order else [start_attraction] + must_visit
    
    def _heuristic_optimize(self, start_attraction: int, must_visit: List[int]) -> List[int]:
        """
        启发式算法优化（最近邻 + 2-opt）
        适用于大量景点（>6个）
        """
        if not must_visit:
            return [start_attraction]
        
        # 第一步：使用最近邻算法构建初始路径
        path = self._nearest_neighbor(start_attraction, must_visit)
        
        # 第二步：使用2-opt算法优化路径
        optimized_path = self._two_opt_optimize(path)
        
        return optimized_path
    
    def _nearest_neighbor(self, start: int, must_visit: List[int]) -> List[int]:
        """
        最近邻算法：每次选择距离当前节点最近的未访问节点
        """
        path = [start]
        unvisited = set(must_visit)
        current = start
        
        while unvisited:
            nearest = None
            nearest_weight = float('inf')
            
            for neighbor in unvisited:
                if current in self.graph and neighbor in self.graph[current]:
                    edge_data = self.graph[current][neighbor]
                    weight = self._calculate_edge_weight(edge_data)
                    
                    if weight < nearest_weight:
                        nearest_weight = weight
                        nearest = neighbor
            
            if nearest:
                path.append(nearest)
                unvisited.remove(nearest)
                current = nearest
            else:
                # 如果找不到路径，添加剩余节点
                path.extend(unvisited)
                break
        
        return path
    
    def _two_opt_optimize(self, path: List[int]) -> List[int]:
        """
        2-opt算法：通过交换路径中的两条边来优化路径
        """
        if len(path) <= 3:
            return path
        
        improved = True
        best_path = path[:]
        best_weight = self._calculate_path_weight(best_path)
        
        max_iterations = 100
        iteration = 0
        
        while improved and iteration < max_iterations:
            improved = False
            iteration += 1
            
            for i in range(1, len(best_path) - 2):
                for j in range(i + 1, len(best_path)):
                    if j - i == 1:
                        continue  # 跳过相邻节点
                    
                    # 尝试交换路径段
                    new_path = best_path[:i] + best_path[i:j+1][::-1] + best_path[j+1:]
                    new_weight = self._calculate_path_weight(new_path)
                    
                    if new_weight < best_weight:
                        best_path = new_path
                        best_weight = new_weight
                        improved = True
                        break
                
                if improved:
                    break
        
        return best_path
    
    def _calculate_path_weight(self, path: List[int]) -> float:
        """
        计算路径的总权重
        """
        if len(path) < 2:
            return 0.0
        
        total_weight = 0.0
        
        for i in range(len(path) - 1):
            from_node = path[i]
            to_node = path[i + 1]
            
            if from_node in self.graph and to_node in self.graph[from_node]:
                edge_data = self.graph[from_node][to_node]
                total_weight += self._calculate_edge_weight(edge_data)
            else:
                # 如果路径不存在，返回很大的权重
                return float('inf')
        
        return total_weight
    
    def _calculate_edge_weight(self, edge_data: Dict) -> float:
        """
        计算边的权重
        """
        distance = float(edge_data.get('distance', 0))
        cost = float(edge_data.get('cost', 0))
        time = edge_data.get('time', 0)
        popularity = edge_data.get('popularity', 0)
        
        return self.weight_config.calculate_weight(distance, cost, time, popularity)

